Condoleezza Rice berusaha memujuk Israel berundur dari wilayah-wilayah Palestin dan membenarkan aliran perdagangan dan perjalanan antara du kawasan terbabit.

Pada 2005, atas gesaan Rice, Israel telah berundur dari tebing Gaza dan sebahagian Tebing Barat. Pada April 2005, beliau berusaha sokongan pemimpin-pemimpin Arab. Pada November 2005, sempadan Gaza berjaya dibuka. Rice melawat Baitulmuqaddis pada 14 November .

Pada September 2007, Rice berjaya mempertemukan Perdana Menteri Israel, Ehud Olmert dengan Presiden Palestin, Mahmoud Abbas di Baitulmuqaddis.

Selepas kematian Yasser Arafat, Rice cuba menekankan pilihan raya lebih demokrasi di Palestin. Setiap warga Palestin hendaklah dilibatkan dalam pilihan raya kerana ia adalah kunci mencipta keamanan di Timur Tengah. Hamas dilabel sebagai kumpulan pengganas.In kerana Hamas pada satu ketika adalah parti politik, sementara pada masa lain terbabit dalam keganasan.

Rice setiap penduduk Palestin di Timur Baitulmuqaddis mengundi dalam pilihan raya Pihak Berkuasa Palestin pada 25 Januari 2006. Rice mengucapkan tahniah kepada Presiden Abbas walaupun Hamas yang menang dalam pilihan raya itu.

Rice mahu Hamas mengiktiraf kewujudan Israel, melucutkan senjata militia Hamas dan mencari jalan perdamaian. Apabila Hamas menang dalam pilihan raya, Israel telah menyekat wang kepunyaan penduduk Palestin dan mengekatkan lagi sekatan perjalanan keluar masuk ke Semenanjung Gaza dan Tebing Barat. George Soros menyalahkan Rice kerana enggan berunding dengan Hamas.